package com.ting.test.algorithms.背包类问题;

/**
 * 王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
 * <p>
 * | 主件   | 附件           |
 * | ------ | -------------- |
 * | 电脑   | 打印机，扫描仪 |
 * | 书柜   | 图书           |
 * | 书桌   | 台灯，文具     |
 * | 工作椅 | 无             |
 * <p>
 * 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 **~** 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
 * <p>
 * 设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
 * <p>
 * v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
 * <p>
 * 请你帮助王强设计一个满足要求的购物单。
 */
public class gouwudan {
    public static void main(String[] args) {
        int[][][] w = new int[][][]{};
        int[][] main = new int[][]{{1, 2, 2, 2, 2}, {2, 3}};
        System.out.println(main[0][1]);
        System.out.println(main[1]);

//        int sum_v = f1(w, 0, 10);
//        System.out.println(sum_v);
    }


    /**
     * @param w     组合商品的数组
     * @param index 当前需要判断的商品下标
     * @param rest  当前背包剩余的承重
     * @return 在不花超的情况下，当前商品(index),以及之后的所有商品返回的总的最大价值 -1表示没有这种情况
     */
    private static int f1(int w[][][], int index, int rest) {
        // 超重了
        if (rest < 0) {
            return -1;//表示这种情况是不可取的
        }
        //没超重，但是 没货了
        if (index == w.length) {
            return 0;//表示商品已经装完了
        }

        // 如果只有主商品，没有附件 这种情况就退化到了经典的背包问题
        if (w[index].length == 1) {
            int[][] product = w[index];
            //两种情况
            //1. p1表示不买该主商品,则在后续的所有商品中通过rest能够买到的的最大价值
            int p1 = f1(w, index + 1, rest);
            //2. 买该商品
            int p2 = -1;//默认不存在这种情况
            int next = f1(w, index + 1, rest - product[0][0]);
            if (next != -1) {
                p2 = product[0][1] * product[0][1] + next;
            }
            return Math.max(p1, p2);

        } else if (w[index].length == 2) {
            // 如果有主商品和1个附件

            int[][] product = w[index];
            //3种情况
            //不买
            //1. p1表示不买该主商品,则在后续的所有商品中通过rest能够买到的的最大价值
            int p1 = f1(w, index + 1, rest);
            //只买主商品
            //2. 只买主商品
            int p2 = -1;//默认不存在这种情况
            int next = f1(w, index + 1, rest - product[0][0]);
            if (next != -1) {
                p2 = product[0][0] * product[0][1] + next;
            }

            //买主商品和第一个附件
            int p3 = -1;//默认不存在这种情况
            int next3 = f1(w, index + 1, rest - product[0][0] - product[1][0]);
            if (next3 != -1) {
                p3 = product[0][0] * product[0][1] + product[1][0] * product[1][1] + next3;
            }
            return Math.max(p1, Math.max(p2, p3));
        } else if (w[index].length == 3) {
            // 如果有主商品和2个附件
            int[][] product = w[index];
            //3种情况
            //不买
            //1. p1表示不买该主商品,则在后续的所有商品中通过rest能够买到的的最大价值
            int p1 = f1(w, index + 1, rest);
            //只买主商品
            //2. 只买主商品
            int p2 = -1;//默认不存在这种情况
            int next = f1(w, index + 1, rest - product[0][0]);
            if (next != -1) {
                p2 = product[0][0] * product[0][1] + next;
            }

            //买主商品和第一个附件
            int p3 = -1;//默认不存在这种情况
            int next3 = f1(w, index + 1, rest - product[0][0] - product[1][0]);
            if (next3 != -1) {
                p3 = product[0][0] * product[0][1] + product[1][0] * product[1][1] + next3;
            }

            //买主商品和第二个附件
            int p4 = -1;//默认不存在这种情况
            int next4 = f1(w, index + 1, rest - product[0][0] - product[2][0]);
            if (next4 != -1) {
                p4 = product[0][0] * product[0][1] + product[2][0] * product[2][1] + next4;
            }

            //买主商品和两个附件
            int p5 = -1;//默认不存在这种情况
            int next5 = f1(w, index + 1, rest - product[0][0] - product[1][0] - product[2][0]);
            if (next5 != -1) {
                p5 = product[0][0] * product[0][1] + product[1][0] * product[1][1] + product[2][0] * product[2][1] + next5;
            }
            return Math.max(Math.max(Math.max(p1, p2), Math.max(p3, p4)), p5);
        } else {
            //不存在这种情况
            return -1;
        }


    }
}
